class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        int candidate = 0;
        int cnt = 0;
        for (int i = 0; i < numbers.size(); i++)
        {
            if (cnt == 0)
            {
                candidate = numbers[i];
                cnt++;
            }
            else
            {
                if (numbers[i] == candidate)
                    ++cnt;
                else
                    --cnt;
            }
        }
        return candidate;
    }
};